// Created by WXX on 2021/10/1 9:50
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：16 ms, 在所有 C++ 提交中击败了33.88%的用户
 * 内存消耗：11.2 MB, 在所有 C++ 提交中击败了17.92%的用户
 */
class Solution {
public:
    string destCity(vector<vector<string>> &paths) {
        unordered_map<string, int> hash;
        for (auto path : paths) {
            auto a = path[0], b = path[1];
            hash[a]++;
            if (!hash.count(b)) hash[b] = 0;
        }
        for (auto &[k, v] : hash)
            if (v == 0)
                return k;
        return "";
    }
};

int main() {

    vector<vector<string>> paths = {
            {"London",   "New York"},
            {"New York", "Lima"},
            {"Lima",     "Sao Paulo"}
    };
    cout << Solution().destCity(paths) << endl;

    return 0;
}
